package problems.daily;

import java.util.Stack;

/**
 * 856. 括号的分数
 * <p>https://leetcode.cn/problems/score-of-parentheses/</p>
 *
 * @author habitplus
 * @since 2022/10/9 09:31
 */
public class DT856 {
    public int scoreOfParentheses(String s) {
        if (s == null || s.length() < 2) return 0;

        char[] chs = s.toCharArray();
        int n = chs.length;

        Stack<Integer> stack = new Stack<>();

        int ret = 0;

        for (int i = 0; i < n; ++i) {
            if (chs[i] == '(') {
                // 当前括号的【分数】入栈，分数默认为 1
                stack.push(1);
            } else {
                // 当前括号的分数
                int cur = stack.pop();
                if (!stack.isEmpty()) {
                    // 说明在内层括号内，先取父括号的分数
                    // 如果父括号的分数为 1，那么当前括号是第一个孩子，即 pa = 2 * cur
                    // 否则，pa += 2 * cur;
                    int pa = stack.pop();
                    pa = pa == 1 ? 2 * cur : pa + 2 * cur;
                    // 父括号继续入栈，便于后续的计算
                    stack.push(pa);
                } else {
                    // 没有父括号，则直接累加到结果上
                    ret += cur;
                }
            }
        }

        if (!stack.isEmpty()) ret += stack.peek();

        return ret;
    }
}
